/*
 * Author: JacksonCoder
 * FileName: TreeNode
 * Version: 1.0.0
 * Date: 2025/2/16
 */

class Node {
    int val;
    Node left;
    Node right;

    Node(int x) {
        val = x;
    }
}

public class TreeNode {

    private int count = 0; // 用于计数已遍历的节点
    private int result = Integer.MIN_VALUE; // 存储第k个小的元素

    public int kthSmallest(Node root, int k) {
        inOrderTraverse(root, k);
        return result;
    }

    private void inOrderTraverse(Node node, int k) {
        if (node == null) {
            return;
        }

        // 先遍历左子树
        inOrderTraverse(node.left, k);

        // 访问节点
        count++;
        if (count == k) {
            result = node.val;
            return; // 找到第k个小的元素后返回
        }

        // 遍历右子树
        inOrderTraverse(node.right, k);
    }

}
